package summary;

import java.util.*;

/**
 * @Author: 海琳琦
 * @Date: 2022/7/11 10:02
 */
public class Title815II {

    public int numBusesToDestination(int[][] routes, int source, int target) {
        if (source == target) {
            return 0;
        }
        LinkedList<Integer> queue = new LinkedList<>();
        //路过该公交站点时的step数 <busId, step>
        Map<Integer, Integer> stepGraph = new HashMap<>();
        //<车站号, 线路号>
        Map<Integer, List<Integer>> routeGraph = new HashMap<>();
        for (int i = 0; i < routes.length; i++) {
            for (int station : routes[i]) {
                //同一层的起点
                if (station == source) {
                    queue.offer(i);
                    stepGraph.put(i, 1);
                }
                routeGraph.computeIfAbsent(station, g -> new ArrayList<>()).add(i);
            }
        }
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Integer busId = queue.poll();
                Integer step = stepGraph.get(busId);
                for (int station : routes[busId]) {
                    if (station == target) {
                        return step;
                    }
                    for (Integer bus : routeGraph.get(station)) {
                        if (!stepGraph.containsKey(bus)) {
                            stepGraph.put(bus, step + 1);
                            queue.offer(bus);
                        }
                    }
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {

    }
}
